1. Field of the Invention
The invention broadly relates to an improved expert system method. In particular, an improved method for organizing objects in a RETE pattern matching network is disclosed.
2. Background Art
Many expert system development shells make use of the RETE pattern matching algorithm. The RETE algorithm itself is well know in the artificial intelligence community. Detailed information on the RETE algorithm can be obtained from the following references: A. Gupta and C.L. Forgy, Measurements On Production Systems, Technical Report CMU-CS-83-167, Carnegie Mellon University, 1983; C.L. Forgy, RETE: A Fast Algorithm For The Many Pattern/Many Object Pattern Match Problem, Artificial Intelligence (1982), pp. 17-37; and M.I. Shore, T.P. Daley, H.S. Lee and B.R. Tibbits, Advances In RETE Pattern Matching, Proceedings of AAAI-86, the disclosures of which are hereby incorporated by reference.
In addition, the following patents/patent application also are pertinent to the RETE pattern matching algorithm: Ser. No. 515,843, entitled "A System And Method For Building A Computer-Based RETE Pattern Matching Network," filed on Apr. 27, 1990 by C.R. Grady F.D. Highland C.T. Iwaskiw, and M.S. Pfiefer, U.S. Pat. No. 4,924,408 entitled "Technique For Compilation of Knowledge Bases" by F.D. Highland, and Ser. No. 515,720, entitled "A Method For Integrating Backward And Forward Chaining Reasoning," filed on Apr. 26, 1990 by H. Gallivan, J.D. Tani, C.T. Iwaskiw, and F.D. Highland, all of which are commonly assigned to the assignee of this invention. The disclosures of the patents/patent applications are all incorporated by reference.
The RETE network is nothing more than a filtration process. A rule is broken into discrete sub-expressions and a RETE noted is built for each of those sub-expressions. Each node performs one task on any data coming into it and broadcasts the results of that test on to the rest of the network. The results which fall out of the bottom of the network are the results of the overall rule. Thus, the RETE algorithm is nothing more than a "divide and conquer" strategy
Expressions consisting of tests involving one or more variables are represented in a RETE network by either one input nodes (known as Alpha nodes) or two input nodes (known as Beta nodes). Consider the following examples
1. (A:car) IF A.door=4 THEN . . . translation: if there exists an A in the universe of cars such that A has 4 doors, then say "we have a 4 door car." (i.e., rule is true if a 4 door car is found.) PA1 2. (A:car, B:truck) IF A.color=B.color THEN . . . translation: if there exists an A in the universe of cars and there exists a B in the universe of trucks such that A has the same color as B then say "we have a pair of vehicles with the same color." (i.e., rule is true if a car/truck pair has the same color.)
These two rules would appear in the RETE network as shown in FIGS. 1A and 1B, respectively. In both cases, these RETE nodes work as filters. All of the relevant data goes into them, but only that data meeting a certain criterion comes out. In other words, only a subset of A's survive the Alpha node and only a subset of the pairs A-B survive the Beta node.
If more than two variables are required in a test, successive variables are combined in one or more AND nodes. When all of the required data is available at two points in the RETE net, the two points are connected into a Beta node. A test involving A, B and C would appear as shown in FIG. 2. An Alpha node might attached underneath another Alpha node which tests another aspect of the same variable. Anything that survives the second Alpha node will have survived the first Alpha node as well.
Large RETE networks can be constructed from Alpha and Beta nodes, as well known in the art. RETE networks may be used to implement the semantics of positively quantified expressions (e.g., there exists on A), negatively quantified expressions (e.g., it is not the case that there exists on A), and mixed quantified expressions (e.g., there exists on A while there does not exist on B).
While RETE networks work well in performing expert reasoning, they can be somewhat cumbersome to process due to variations in their organizational structure in the network. This variation stems from the arbitrory ordering of conditions in a rule which can directly impact the performance of the resultant RETE network. It is desirable to have a method for organizing objects in a RETE network to further improve the inferencing speeds of an expert system.